# LeetCode 36、有效的数独
# 一、题目描述
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
注意：
- 一个有效的数独（部分已被填充）不一定是可解的。
- 只需要根据以上规则，验证已经填入的数字是否有效即可。
- 空白格用
'.'表示。
示例 1：
img
输入：board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true
示例 2：
输入：board =
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
提示：
board.length == 9board[i].length == 9board[i][j]是一位数字（1-9）或者'.'
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 添加微信 278166530 获取最新课程
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 有效的数独（LeetCode 36）：https://leetcode.cn/problems/valid-sudoku/
class Solution {
public boolean isValidSudoku(char[][] board) {
// 使用哈希表记录每一行每个数字出现的次数
// 由于数字是从 1 - 9 ，因此可以采取数组的形式来表示哈希表
// 即利用数组的索引作为哈希表的 key ， 数组的元素值作为哈希表的 value
int[][] rows = new int[9][9];
// 使用哈希表记录每一列每个数字出现的次数
// 由于数字是从 1 - 9 ，因此可以采取数组的形式来表示哈希表
// 即利用数组的索引作为哈希表的 key ， 数组的元素值作为哈希表的 value
int[][] columns = new int[9][9];
// 使用哈希表记录每一个【小九宫格】每个数字出现的次数
// 由于数字是从 1 - 9 ，因此可以采取数组的形式来表示哈希表
// 即利用数组的索引作为哈希表的 key ， 数组的元素值作为哈希表的 value
int[][][] subboxes = new int[3][3][9];
// 一行行一列列去访问二维矩阵 board 的每个元素
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
// 获取当前小方格的字符
char c = board[i][j];
// 如果不是空白格而是数字
if (c != '.') {
// 由于数组的索引是从 0 开始的，而小方格的值是从 1 开始的
// 因此，索引 0 代表 key 为 1
// 索引 1 代表 key 为 2
// 所以，c 为 9 时，存储在索引为 8 的位置
// c 为 6 时，存储在索引为 5 的位置
int index = c - '0' - 1;
// 第 i 行数字 index 出现的次数增加 1 次
rows[i][index]++;
// 第 j 列数字 index 出现的次数增加 1 次
columns[j][index]++;
// 总共有 9 个 3 * 3 的小九宫格
// 第一行有 3 个，包含了第 0 个、第 1 个、第 2 个
// 第二行有 3 个，包含了第 3 个、第 4 个、第 5 个
// 第三行有 3 个，包含了第 6 个、第 7 个、第 8 个
// (i / 3 , j / 3) 表示是第几个小九宫格
// 当前这个小九宫格里面数字 index 出现的次数增加 1 次
subboxes[i / 3][j / 3][index]++;
// 如果发现如下任何一种情况，都说明是无效的
// 1、这一行统计出 index 数字的次数大于 1 个
// 2、这一列统计出 index 数字的次数大于 1 个
// 3、这一小九宫格统计出 index 数字的次数大于 1 个
if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) {
// 返回 false
return false;
}
}
}
}
// 是有效的，返回 true
return true;
}
}
# **2、**C++ 代码
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
// 使用哈希表记录每一行每个数字出现的次数
// 由于数字是从 1 - 9 ，因此可以采取数组的形式来表示哈希表
// 即利用数组的索引作为哈希表的 key ， 数组的元素值作为哈希表的 value
int rows[9][9];
memset(rows,0,sizeof(rows));
// 使用哈希表记录每一列每个数字出现的次数
// 由于数字是从 1 - 9 ，因此可以采取数组的形式来表示哈希表
// 即利用数组的索引作为哈希表的 key ， 数组的元素值作为哈希表的 value
int columns[9][9];
memset(columns,0,sizeof(columns));
// 使用哈希表记录每一个【小九宫格】每个数字出现的次数
// 由于数字是从 1 - 9 ，因此可以采取数组的形式来表示哈希表
// 即利用数组的索引作为哈希表的 key ， 数组的元素值作为哈希表的 value
int subboxes[3][3][9];
memset(subboxes,0,sizeof(subboxes));
// 一行行一列列去访问二维矩阵 board 的每个元素
for (int i = 0 ; i < 9 ; i++) {
for (int j = 0 ; j < 9 ; j++) {
// 获取当前小方格的字符
char c = board[i][j];
// 如果不是空白格而是数字
if (c != '.') {
// 由于数组的索引是从 0 开始的，而小方格的值是从 1 开始的
// 因此，索引 0 代表 key 为 1
// 索引 1 代表 key 为 2
// 所以，c 为 9 时，存储在索引为 8 的位置
// c 为 6 时，存储在索引为 5 的位置
int index = c - '0' - 1;
// 第 i 行数字 index 出现的次数增加 1 次
rows[i][index]++;
// 第 j 列数字 index 出现的次数增加 1 次
columns[j][index]++;
// 总共有 9 个 3 * 3 的小九宫格
// 第一行有 3 个，包含了第 0 个、第 1 个、第 2 个
// 第二行有 3 个，包含了第 3 个、第 4 个、第 5 个
// 第三行有 3 个，包含了第 6 个、第 7 个、第 8 个
// (i / 3 , j / 3) 表示是第几个小九宫格
// 当前这个小九宫格里面数字 index 出现的次数增加 1 次
subboxes[ i / 3 ][j / 3 ][index]++;
// 如果发现如下任何一种情况，都说明是无效的
// 1、这一行统计出 index 数字的次数大于 1 个
// 2、这一列统计出 index 数字的次数大于 1 个
// 3、这一小九宫格统计出 index 数字的次数大于 1 个
if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i/3][j/3][index] > 1) {
// 返回 false
return false;
}
}
}
}
// 是有效的，返回 true
return true;
}
};
# 3、Python 代码
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
# 使用哈希表记录每一行每个数字出现的次数
rows = [[0] * 9 for _ in range(9)]
# 使用哈希表记录每一列每个数字出现的次数
columns = [[0] * 9 for _ in range(9)]
# 使用哈希表记录每一个【小九宫格】每个数字出现的次数
subboxes = [[[0] * 9 for _ in range(3)] for _ in range(3)]
for i in range(9):
for j in range(9):
c = board[i][j]
if c != '.':
c = int(c) - 1
rows[i][c] += 1
columns[j][c] += 1
subboxes[int(i/3)][int(j/3)][c] += 1
if rows[i][c] > 1 or columns[j][c]>1 or subboxes[int(i/3)][int(j/3)][c]>1:
return False
return True